package com.practice.niuke.new_direct_practice.class09;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个数组arrx和arry， 长度都为N。 代表二维平面上有N个点， 第i个点的x 坐标和y坐标
 * 分别为arrx[i]和arry[i]， 返回求一条直线最多能穿过多少个点?
 */
public class Code02_MaxPointsOneLine {

	/**
	 * 点类型
	 */
	public static class Point {
		public int x;
		public int y;

		Point() {
			x = 0;
			y = 0;
		}

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

	/**
	 * 返回求一条直线最多能穿过多少个点(TODO: 标记重点，起始代码读取位置)
	 *
	 * @param points 点数组
	 * @return 一条直线最多能穿过多少个点
	 */
	public static int maxPoints(Point[] points) {

		if (points == null) {
			// 点数组为null时，直接返回0
			return 0;
		}

		if (points.length <= 2) {
			// 点数组中点的数量小于等于2，直接返回数组的长度（两点确定一条直线嘛！！！）
			return points.length;
		}

		// Map<String, Integer>
		// key:  3   ->  ( 5  ,  6   )
		// key:          ( 7,  4    )
		// key:          ( 11,  8    )
		//  3/5    6
		//  3/7    4
		//  3/11   8
		Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();

		int result = 0;
		for (int i = 0; i < points.length; i++) { // 直线必须从i号点出发，考察i后面的点和i的关系
			map.clear();
			// 与i号点共位置
			int samePosition = 1;
			// 与i号点共竖线
			int sameX = 0;
			// 与i号点共横线
			int sameY = 0;
			// 所有斜率中压中点最多的
			int line = 0;
			// i（固定）......
			for (int j = i + 1; j < points.length; j++) {
				int x = points[j].x - points[i].x;
				int y = points[j].y - points[i].y;
				if (x == 0 && y == 0) {
					// 共位置
					samePosition++;
				} else if (x == 0) {
					// 共竖线
					sameX++;
				} else if (y == 0) {
					// 共横线
					sameY++;
				} else {  // 有斜率
					// 求最大公约数
					int gcd = gcd(x, y);
					x /= gcd;
					y /= gcd;
					if (!map.containsKey(x)) {
						map.put(x, new HashMap<Integer, Integer>());
					}
					if (!map.get(x).containsKey(y)) {
						map.get(x).put(y, 0);
					}
					// x/y
					map.get(x).put(y, map.get(x).get(y) + 1);
					line = Math.max(line, map.get(x).get(y));
				}
			}
			result = Math.max(result, 
					          Math.max(Math.max(sameX, sameY), line) + samePosition);
		}
		return result;
	}

	/**
	 * 求两个数的最大公约数，时间复杂度 O(1)
	 * 前提：保证初始调用的时候，a和b不等于0
	 *
	 * @param a a
	 * @param b b
	 * @return int
	 */
	public static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

}
